package 贪心;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 数组大小减半.java
 * @Description TODO
 * @createTime 2020年10月20日 15:27:00
 * 给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。
 *
 * 返回 至少 能删除数组中的一半整数的整数集合的最小大小。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：arr = [3,3,3,3,5,5,5,2,2,7]
 * 输出：2
 * 解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
 * 大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
 * 选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。
 *
 思路：很简单 统计每个数出现的次数 降序 依次减 直到符合题目
 */
public class 数组大小减半 {
    public static void main(String[] args) {
        int[] arr={1,2,3,4,5,6,7,8,9,10};
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int a:arr){
            map.put(a, map.getOrDefault(a, 0)+1);//如果没有为0 如果有就++
        }




        ArrayList<Integer> list=new ArrayList<>();
        for(int a:map.keySet()){
        list.add(map.get(a));
        }
        list.sort(Comparator.reverseOrder());
        int sum=0;
        for(int i=0;i<list.size();i++){
            sum+=list.get(i);
            if(sum>=arr.length/2){
                System.out.println(i+1);
            }
        }

    }
}
